#include <iomanip>
#include <iostream>
using namespace std;

void FillRand(int A[], int n);
void RunNumber(int A[], int n);
void CheckSum(int A[], int n);
void FillInc(int A[], int n);
void FillDec(int A[], int n);
int BubbleSort(int A[], int n, int check);

int main() {
    int n = 100;
    int A[n];
    int check = 0;
    
    // рандомный
    srand(time(NULL));
    cout << "Рандомный массив: " << endl;
    FillRand(A, n);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);
    int k_rand = BubbleSort(A, n, check);
    cout << "М теория: " << 3*((n*n-n)/2)/2 << endl;
    cout << "C теория: " << (n*n-n)/2 << endl;
    
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);

    // возрастающий
    cout << endl
         << "Возрастающий массив: " << endl;
    FillInc(A, n);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);
    int k_vozv = BubbleSort(A, n, check);
    cout << "М теория: 0" << endl;
    cout << "C теория: " << (n*n-n)/2 << endl;
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);

    // убывающий
    cout << endl
         << "Убывающий массив: " << endl;
    FillDec(A, n);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);
    int k_yb = BubbleSort(A, n, check);
    cout << "М теория: " << (n*(n-1))/2 << endl;
    cout << "C теория: " << (n*n-n)/2 << endl;
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);
    
    //рисунок
    // 100
    cout << setw(15) << " " << setw(15) << "Трудоёмкость " << setw(15) << "пузырьковой " << setw(15) << "сортировки" << endl;
    cout << setw(60) << "------------------------------------------------------------" << endl;
    cout << setw(2) << "n" << setw(12) << "M+C" << setw(32) << "Мф+Сф" << endl;
    cout << setw(26) << "теоритич " << setw(43) << "убыв  случ   возр" << endl;
    cout << setw(2) << n << setw(12) << ((n*n-n)/2)+(((n*n-n)/2)*3/2) << setw(21) << k_yb << setw(6) << k_rand << setw(7) << k_vozv << endl;
    // 200
    n = 200, check = 1;
    int B[n];
    FillRand(B, n);
    k_rand = BubbleSort(B, n, check);
    FillInc(B, n);
    k_vozv = BubbleSort(B, n, check);
    FillDec(B, n);
    k_yb = BubbleSort(B, n, check);

    cout << setw(2) << n << setw(12) << ((n*n-n)/2)+(((n*n-n)/2)*3/2) << setw(21) << k_yb << setw(7) << k_rand << setw(7) << k_vozv << endl;
    
    // 300
    n = 300;
    int C[n];
    FillRand(C, n);
    k_rand = BubbleSort(C, n, check);
    FillInc(C, n);
    k_vozv = BubbleSort(C, n, check);
    FillDec(C, n);
    k_yb = BubbleSort(C, n, check);

    cout << setw(2) << n << setw(12) << ((n*n-n)/2)+(((n*n-n)/2)*3/2) << setw(21) << k_yb << setw(7) << k_rand << setw(7) << k_vozv << endl;
    
    // 400
    n = 400;
    int D[n];
    FillRand(D, n);
    k_rand = BubbleSort(D, n, check);
    FillInc(D, n);
    k_vozv = BubbleSort(D, n, check);
    FillDec(D, n);
    k_yb = BubbleSort(D, n, check);

    cout << setw(2) << n << setw(12) << ((n*n-n)/2)+(((n*n-n)/2)*3/2) << setw(21) << k_yb << " " << setw(7) << k_rand << " " << setw(4) << k_vozv << endl;
    
    // 500
    n = 500;
    int E[n];
    FillRand(E, n);
    k_rand = BubbleSort(E, n, check);
    FillInc(E, n);
    k_vozv = BubbleSort(E, n, check);
    FillDec(E, n);
    k_yb = BubbleSort(E, n, check);

    cout << setw(2) << n << setw(12) << ((n*n-n)/2)+(((n*n-n)/2)*3/2) << setw(21) << k_yb << " " << setw(7) << k_rand << " " << setw(4) << k_vozv << endl;
}

int BubbleSort(int A[], int n, int check) {
    int M = 0, C = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            C++;
            if (A[j] > A[j + 1]) {
                swap(A[j], A[j + 1]);
                M++;
            }
        }
    }
    if (check == 0){
        cout << "М по факту: " << M << endl;
        cout << "C по факту: " << C << endl;
    }
    return M+C;
}

void FillRand(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = rand() % 1000;
    }
}

void RunNumber(int A[], int n) {
    int r = 1;
    for (int i = 1; i < n; i++) {
        if (A[i - 1] > A[i])
            r++;
    }
    cout << "Серий: " << r << endl;
}

void CheckSum(int A[], int n) {
    long int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += A[i];
    }
    cout << "Сумма: " << sum << endl;
}

void FillInc(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = i + 1;
    }
}

void FillDec(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = n - i;
    }
}




